//我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。 
//
// 
// 例如，如果 nums1 = [1,2,3,8] ， nums2 =[5,6,7,4] ，你可以交换 i = 3 处的元素，得到 nums1 =[1,2,3
//,4] 和 nums2 =[5,6,7,8] 。 
// 
//
// 返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。 
//
// 数组 arr 严格递增 且 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。 
//
// 注意： 
//
// 
// 用例保证可以实现操作。 
// 
//
// 
//
// 示例 1: 
//
// 
//输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
//输出: 1
//解释: 
//交换 A[3] 和 B[3] 后，两个数组如下:
//A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
//两个数组均为严格递增的。 
//
// 示例 2: 
//
// 
//输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
//输出: 1
// 
//
// 
//
// 提示: 
//
// 
// 2 <= nums1.length <= 10⁵ 
// nums2.length == nums1.length 
// 0 <= nums1[i], nums2[i] <= 2 * 10⁵ 
// 
// Related Topics数组 | 动态规划 
//
// 👍 343, 👎 0 
//
//
//
//

package leetcode.editor.day;

// 801. 使序列递增的最小交换次数
// https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/
class MinimumSwapsToMakeSequencesIncreasing {
    public static void main(String[] args) {
        Solution solution = new MinimumSwapsToMakeSequencesIncreasing().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minSwap(int[] nums1, int[] nums2) {
            int n = nums1.length;
            // 条件一: n1[i] > n1[i - 1] && n2[i] > n2[i - 1]
            // 条件二: n1[i] > n2[i - 1] && n2[i] > n1[i - 1]

            // dp[i][0]:表示对于位置i的索引，不进行交换的最少操作次数
            // dp[i][1]:表示对于位置i的索引，进行交换的最少操作次数
            int[][] dp = new int[n][2];
            // 可以用变量代替，减少空间复杂度
            for (int i = 1; i < n; i++) {
                if ((nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) && (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1])) {
                    // 满足条件1，2；例如: 13 24 怎么交换都行，取最小的操作数
                    dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]);
                    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
                } else if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                    // 满足条件2；例如: 15 43 此时交换 i - 1
                    dp[i][0] = dp[i - 1][1];
                    dp[i][1] = dp[i - 1][0] + 1;
                } else if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                    // 满足条件1；例如: 12 34 要么i和i-1同时交换，要么不交换
                    dp[i][0] = dp[i - 1][0];
                    dp[i][1] = dp[i - 1][1] + 1;
                }
            }

            return Math.min(dp[n - 1][0], dp[n - 1][1]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
